[Datenschleuder] [44]    RSA

RSA (Sorry, aber in diesem Text sind noch TeX-Reste über - Der Editor) Thema: Datensicherheit. Verschlüsselung mit dem RSA-Code. Theoretisches. Quelle: Vorlesung über Lineare Algebra, Paderborn. Das "public key"- System von R. L. Riverest, A. Shamir, L. M. Adleman (1978) (RSA- Code): Die Benutzer eines öffentlichen Kommunikativsystems wollen verschlüsselte Botschaften austauschen. Es wird ein Alphabet mit N Zeichen benutzt. Die Zeichen werden durchnumeriert. Seinen b(0), b(1), ... b(N--1) die Buchstaben in diesem Alphabet. Diese Reihenfolge wird beibehalten. Man wählt natürliche Zahlen k und l mit k $<$ l, für die N\^{} k (N hoch k) und N^l (N hoch l) ca. 200 Dezimalstellen haben. Das Alphabet, die Reihenfolge der Zeichen, die Zahl N, und die Zahlen k und l werden veröffentlicht. (1) Erzeugung des Codes Es sei A ein Benutzer dieses Systems. A wählt zwei verschiedene Primzahlen p(A) und q(A) mit jeweils etwa 100 Dezimalstellen, die folgende Bedingung erfüllen : Es ist N^k < p(A) * q(A) < N^l Dann berechnet A die Zahlen m(A) = p(A) * q(A) und phi(A) = (p(A) --1) * (q(A) -- 1) und wählt eine Zahl e(A) zwischen 1 und phi(A)--1, die mit phi(A)--1 keinen gemeinsamen Teiler hat. Anschließend berechnet A die Zahl d(A) für die gilt: Es gibt eine natürliche Zahl k mit : d(A) * e(A) = 1 + phi(A) * k (Mathematisch: d(A) * e(A) ist kongruent zu 1 modulo phi(A)) (Für die Berechnung von d(A) gibt es schnelle Algorithmen. Eingabe dieser Algorithmen ist e(A) und phi(A). Die Geheimhaltung von phi(A) ist also dringend erforderlich, um die Sicherheit des Codes zu garantieren.) Die Zahlen m(A) und e(A) werden veröffentlicht, die Zahlen p(A), q(A), d(A) und phi(A) müssen geheimgehalten werden. p(A), q(A) und phi(A) werden nicht mehr benötigt. (2) Verschlüsselung und Entschlüsselung Der Benutzer B möchte an A eine verschlüsselte Nachricht schicken. B teilt den Klartext in Blöcke aus k Zeichen und ersetzt jedes Zeichen durch sein "numerisches" Äquivalent (also jeweils b(i) durch i). So entstehen k-tupel aus Zahlen in (0, 1, ..., N--1). Es sei (y(1), ..., y(k)) ein solches k-tupel. B berechnet X := y(1) * N\^{} (k--1) + y(2) * N\^{} (k--2) + ... + y(k--1) * N + y(k) und X1 := (X \^{} e(A)) MOD m(a) Es gilt 0 $<$ X $<$ N\^{} k--1 $<$ N\^{} l--1. B berechnet die z(1), ..., z(l) mit X1 = z(1) * N\^{} (l--1) + z(2) * N\^{} (l--2) + ... + z(l--1) * N + z(l). Das l-tupel (z(1), ..., z(l)) wird über das öffentliche Kommunikations- system an A geschickt. A berechnet daraus wieder X1 = z(1) * N\^{} (l--1) + ... + z(l), und dann X2 := (X1 \^{} d(A)) mod m(A). Es gilt: X2 = X. Aus X berechnet A die Zahlen y(1), ..., y(k) mit X := y(1) * N\^{} (k--1) + y(2) * N\^{} (k--2) + ... + y(k--1) * N + y(k) und hat damit (y(1), ..., y(k)) zurückgewonnen, und kann die Original- nachricht daraus zusammensetzen. Anmerkung: Die Gesamtnachricht setzt sich aus den Kodierungen aller k-tupel der Originalnachricht zusammen. Die Nachricht verlängert sich beim kodieren also um das l/k-fache. Zum Kodieren ist die Kenntnis der Zahlen m(A), e(A), k, l, und N sowie die Kodierung der Zeichen im Alphabet notwendig. m(A) und e(A) haben jeweils ca. 200 Stellen und sind somit nur schweer zu merken, oder überall für jeweils alle Benutzer zu speichern. (3) Identifizierung von Nachrichten Jeder Teilnehmer erhält eine Signatur (g(1), ..., g(k)) aus Zeichen des Alphabets zugewiesen, die ihn eindeutig identifiziert (z. B. der Username), und die veröffentlicht ist. B möchte mit seiner Botschaft an A einen Beweis dafür mitschicken, daß die Botschaft von ihm kommt. B berechnet mit seiner eigenen Signatur: s := g(1) * N\^{} (k--1) + g(2) * N\^{} (k--2) + ... + g(k--1) * N + g(k) und s1 := (s \^{} d(B)) mod m(B) und ermittelt daraus die h(1),.. h(l) mit s1 = h(1) * N\^{} (l--1) + h(2) * N\^{} (l--2) + ... + h(l--1) * N + h(l) und schickt (h(1),..., h(l)) mit seiner Botschaft an A. A dechiffriert, wie in (2) beschrieben die eingegangenen l-tupel. Alle ergeben sinnvollen Klartext außer h(1),..., h(l). Hiermit berechnet er wieder s1 := h(1) * N\^{} (l--1) + h(2) * N\^{} (l--2) + ... + h(l--1) * N + h(l) und s := (s1 \^{} e(B)) mod m(B) A schreibt s als: s = g(1) * N\^{} (k--1) + g(2) * N\^{} (k--2) + ... + g(k--1) * N + g(k) und hat damit (g(1), ..., g(k)) berechnet und vergleicht mit der veröffentlichten Signatur im Telefonbuch. Anmerkung: Dieses Verfahren klappt nur dann, wenn man die Position der h(1), ..., h(l) in der verschlüsselten Datei nicht im Vorraus ermitteln kann, und wenn B seine Identität bereits anderswo in der verschlüsselten Datei andeutet. So bietet die hier beschriebene Methode eine Möglichkeit, das Dokument zu "unterschreiben", so da₧ nicht jeder diese Unterschrift unter ein mit falschem Absender versehenen Brief schreiben kann. Wenn die Zahlen h(1), ..., h(l) jedoch einem dritten bekannt werden, so ist das Verfahren hinfällig. Außerdem muß B seine Identität anderswo im Dokument angeben, weil sonst der Empfänger alle Möglichkeiten für verschiedene Absender durchgehen muß. (4) Sicherheit Die Sicherheit des Systems beruht darauf, daß es (noch) keinen schnellen Algorithmus zur Faktorisierung großer natürlicher Zahlen gibt. Um eine an A gerichtete Nachricht zu entschlüsseln benötigt man d(A) und um d(A) zu berechnen benätigt man die Faktorisierung von m(A) = p(A= * q(A). (5) Primzahlen Zur Herstellung von p(A) und q(A) und e(A) hat men einen Generator von Zufallszahlen zu verwenden (und einen schnellen Primzahltest) (6) Zum modernsten Stand - G. Brassard, Modern cryptology, 1988 - E. Kranakis, Primality and cryptography - N. Knoblitz, A course in number theory and cryptogrphy Autor: M.Jung

[Datenschleuder] [44]    RSA